1792. Поиск пароля

Возможность отправлять закодированные сообщения во время Второй мировой войны была достаточно важной для союзников. Сообщения всегда отправлялись после их кодирования при помощи известного пароля. Иметь фиксированный пароль было небезопасно, поэтому возникла необходимость часто изменять его. Однако следовало разработать механизм отправления нового пароля. У одного из математиков, работавших в криптографической команде, возникла умная идея - отправить пароль, скрытый в самом сообщении. Интересным моментом было то, что получателю сообщения достаточно было знать только размер пароля, а потом найти его в полученном тексте.

Пароль размера n можно найти поиском в тексте наиболее часто встречаемой подстроки из n символов. После нахождения пароля все подстроки совпадающие с ним, удаляются из текста. Теперь пароль можно использовать для расшифровки сообщения.

Однако Ваша задача будет упрощена. Вам достаточно написать программу, которая по заданному размеру пароля и закодированному сообщению найдет пароль в соответствии с описанным выше алгоритмом.

Рассмотрим пример, в котором размер пароля равен трем (n = 3), а текст сообщения имеет вид baababacb. Паролем будет aba, потому что размер этой подстроки 3, она появляется чаще всего во всем тексте (дважды), а остальные шесть различных подстрок появляются только один раз (baa, aab, bab, bac, acb).

Вход. Состоит из нескольких тестов. Каждый тест представляет собой одну строку, в которой находится длина пароля n (0 < n ≤ 10) и закодированное сообщение. Сообщение содержит только прописные буквы латинского алфавита, его длина не более 10⁶ и не меньше n.

Выход. Для каждого теста в отдельной строке следует вывести искомый пароль. Если существует несколько паролей, удовлетворяющих задаче, то вывести лексикографически наименьший.

Пример входа	Пример выхода
3 baababacb	aba

РЕШЕНИЕ

строки – хеширование

Анализ алгоритма

Закодируем буквы латинского алфавита: 'a' = 1, 'b' = 2, …, 'z' = 26. Хешем строки s₁s₂…s_n назовем число s₁ * 27^n-1 + s₂ * 27^n-2 +…+ s_n-1 * 27 + s_n. Рассмотрим строку s₁s₂…s_n s_n+1. Пусть хеш подстроки s₁s₂…s_n равен hash. Тогда хеш подстроки s₂…s_n s_n+1 равен (hash mod 27^n-1) * 27 + s_n+1. Таким образом мы можем за О(1) пересчитывать хеш следующей подстроки.

Вычислим хеши всех подстрок длины n и отсортируем их. Лексикографически меньшая подстрока имеет меньший хеш. Находим чаще всего встречаемый хеш (если их несколько – то берем наименьший). Выводим строку, которая ему соответствует.

Пример

Вычислим хеши всех подстрок длины 3 для строки baababacb:

подстрока	хеш
baa	2 * 27^2 + 1 * 27 + 1 = 1486
aab	1 * 27^2 + 1 * 27 + 2 = 758
aba	1 * 27^2 + 2 * 27 + 1 = 784
bab	2 * 27^2 + 1 * 27 + 2 = 1487
aba	1 * 27^2 + 2 * 27 + 1 = 784
bac	2 * 27^2 + 1 * 27 + 3 = 1488
acb	1 * 27^2 + 3 * 27 + 2 = 812

Отсортированное множество хешей имеет вид {758, 784, 784, 812, 1486, 1487, 1488}.

Чаще всего встречаемый хеш – 784, ему соответствует строка “aba”.

Реализация алгоритма

Занесем хеши всех подстрок длины n в массив H. Входную строку читаем в s.

vector<unsigned long long> H;

string s;

Читаем входные данные. Вычисляем длину len строки s.

while (cin >> n)

{

cin >> s; len = s.size();

H.clear();

Вычисляем хеш Hash префикса строки s длины n. Заносим его в массив H. Установим p = 27^n-1.

for (p = 1, Hash = i = 0; i < n; i++, p *= 27)

Hash = Hash * 27 + (s[i] - 'a' + 1);

p /= 27;

H.push_back(Hash);

Вычисляем хеши всех подстрок длины n. Заносим их в массив H.

for (i = 0; i < len - n; i++)

{

Hash %= p;

Hash = Hash * 27 + s[i + n] - 'a' + 1;

H.push_back(Hash);

}

Сортируем хеши.

sort(H.begin(), H.end());

Ищем хеш Hash, который чаще всего встречается в массиве H.

for (d = i = 0; i < H.size(); i = j)

{

for (j = i; j < H.size() && H[j] == H[i]; j++);

if (j - i > d) d = j - i, Hash = H[i];

}

Выводим строку, соответствующую хешу Hash.

while (Hash)

{

cout << (char)(Hash / p + 'a' - 1);

Hash %= p, p /= 27;

}

cout << endl;

}